package gitdemo1.git3.demo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;

public class Solution {
    public static void main(String[] args) {

    }
    public static int f(int N,int E,int rest,int cur){
        //int res=0;
        if(rest==0){
            return E==cur? 1:0;
        }

        if(cur==1){
          return   f(N, E, rest-1, 2);
        }

        if(cur==N){
          return   f(N, E, rest-1, N-1);
        }
        return f(N, E, rest-1, cur+1)+f(N, E, rest-1, cur-1);
    }

    public static int walkWay(int N,int E,int rest,int cur){
        int dp[][]=new int[rest+1][cur+1];
        for (int i = 0; i <=rest; i++) {
            for (int j = 0; j <=cur; j++) {
                dp[i][j]=-1;
            }
        }
       return f2(N,E,rest,cur,dp);

    }

    private static int f2(int N,int E,int rest,int cur,int dp[][]) {
        if(cur>dp.length||rest>dp[0].length){
            return -1;
        }
        if(dp[rest][cur]!=-1){
            return dp[rest][cur];
        }
        if(rest==0){
            dp[rest][cur]=cur==E?1:0;
            return dp[rest][cur];
        }
        //
        if(cur==1){
            dp[rest][cur]=f(N, E, rest-1, 2);
        }else if(cur==N){
            dp[rest][cur]=f(N, E, rest-1, N-1);
        }else {
            dp[rest][cur]=f(N, E, rest-1, cur+1)+f(N, E, rest-1, cur-1);
        }
        return dp[rest][cur];
    }


}
